The present invention generally relates to the physical design of electronic devices, and, more particularly, to channel routing.
Computer aided design plays a key role in providing electronic circuits with very large scale integration (VLSI) on the market. A useful reference is [1] Naveed Sherwani: xe2x80x9cAlgorithms for VLSI Physical Design Automationxe2x80x9d, Second Edition, Kluwer Academic Publishers, Boston, Dordrecht, London, 1995, ISBN 0-7923-9592-1. According to reference [1], the VLSI design cycle usually comprises system specification, functional design, logic design, circuit design, physical design, fabrication, packaging, testing and debugging. The physical design level has several stages, such as partitioning, floorplanning, placement, routing, and compaction. Iterations are common so that some steps are performed twice or more often. In the placement stage, the exact locations of circuit blocks and their terminals are determined and a list for interconnection nets (i.e. a netlist) between the terminals is generated. Routing is the process of finding geometric layouts for all nets in so-called routing regions between the blocks.
A channel is conveniently referred to in the art as a routing region bounded by two parallel rows of terminals. The distance between the rows, often referred to as xe2x80x9cchannel heightxe2x80x9d, should be minimized to save silicon. The estimation of the channel height is very important for floorplanning iterations.
Further references for channel routing are: [2] Akihiro Hashimoto and James Stevens: xe2x80x9cWire routing by optimizing channel assignment within large aperturesxe2x80x9d, Proceedings of the 8th Design Automation Workshop, 1971, pages 155-169; [3] David N. Deutsch: xe2x80x9cA xe2x80x98Doglegxe2x80x99 Channel Routerxe2x80x9d, Proceedings of the 13th Design Automation Workshop, 1976, pages 425-433; [4] Howard H. Chen and Ernest S. Kuh: xe2x80x9cGlitter: A Gridless Variable-Width Channel Routerxe2x80x9d, IEEE Transactions on Computer-Aided Design, vol. CAD-5. No. 4, October 1986, pages 459-465; [5] James Reed, Alberto Sangiovanni-Vincentelli and Mauro Santomauro: xe2x80x9cA New Symbolic Channel Router: YACR2xe2x80x9d, IEEE Transactions on Computer-Aided Design, vol. CAD-4, No. 3, July 1985, pages 208-219; and [6] Bryan Preas: xe2x80x9cChannel Routing With Non-Terminal Doglegsxe2x80x9d, Proceedings of European Design Automation Conference, Glasgow, Scotland, 1990, pages 451-458.
The present invention seeks to provide an improved method to optimize channel routing which mitigates or avoids disadvantages and limitations of the prior art.